package algorithm.sort;

/**
 * 插入排序
 */
public class InsertionSort {

    public int[] sortArray(int[] nums){
        if (nums.length == 0){
            return nums;
        }
        int currentValue;//当前等待排序元素，该元素之前已经排序过
        for (int i = 0; i < nums.length - 1; i++) {
            int preIndex = i;//已被排序的数据的索引
            currentValue = nums[preIndex + 1];
            /**
             * 在已经被排序的元素中寻找合适的位置，如果当前排序数据比要比较的的元素要小，将比较的元素后一一位
             */
            while (preIndex >= 0 && currentValue < nums[preIndex] ){
                nums[preIndex+1] = nums[preIndex];
                preIndex --;
            }
            //while循环结束，说明已经找到了当前待排序数组的合适位置，插入
            nums[preIndex + 1] = currentValue;
        }

        return nums;
    }
}
